/*
 * @Author: szx
 * @Date: 2021-11-01 14:09:10
 * @LastEditTime: 2021-11-01 14:33:27
 * @Description:
 * @FilePath: \leetcode\600-699\695\695.cpp
 */
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

class Solution {
   public:
    const int dx[4] = {1, 0, 0, -1};
    const int dy[4] = {0, 1, -1, 0};
    int dfs(vector<vector<int>>& grid, int cur_i, int cur_j) {
        if (grid[cur_i][cur_j] == 1) {
            int cnt = 1;
            grid[cur_i][cur_j] = 0;
            for (int a = 0; a < 4; a++) {
                int mx = cur_i + dx[a], my = cur_j + dy[a];
                if (mx >= 0 && mx < grid.size() && my >= 0 &&
                    my < grid[0].size() && grid[mx][my] == 1) {
                    cnt += dfs(grid, mx, my);
                }
            }
            return cnt;
        }
        return 0;
    }
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int max = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] != 0) {
                    int cnt = dfs(grid, i, j);
                    if (cnt > max) {
                        max = cnt;
                    }
                }
            }
        }
        return max;
    }
};

// class Solution {
//    public:
//     const int dx[4] = {1, 0, 0, -1};
//     const int dy[4] = {0, 1, -1, 0};
//     int maxAreaOfIsland(vector<vector<int>>& grid) {
//         int n = grid.size();
//         int m = grid[0].size();
//         queue<pair<int, int>> que;
//         int max = 0;
//         for (int i = 0; i < n; i++) {
//             for (int j = 0; j < m; j++) {
//                 if (grid[i][j] != 0) {
//                     que.emplace(i, j);
//                     grid[i][j] = 0;
//                     int cnt = 0;
//                     while (!que.empty()) {
//                         int x = que.front().first, y = que.front().second;
//                         que.pop();
//                         cnt++;
//                         for (int a = 0; a < 4; a++) {
//                             int mx = x + dx[a], my = y + dy[a];
//                             if (mx >= 0 && mx < n && my >= 0 && my < m &&
//                                 grid[mx][my] == 1) {
//                                 que.emplace(mx, my);
//                                 grid[mx][my] = 0;
//                             }
//                         }
//                     }
//                     if (cnt > max) {
//                         max = cnt;
//                     }
//                 }
//             }
//         }
//         return max;
//     }
// };

int main() { return 0; }